/*
 * search.cpp
 *
 *  Created on: 15.03.2013
 *      Author: valya
 */

#include "my_search.h"
#include <vector>
#include <algorithm>

typedef tree_t::Node Node;
typedef Node::adv_point adv_point;


point_t::point_t(double x_, double y_): x(x_), y(y_) {};

point_t::point_t(const point_t &p): x(p.x), y(p.y) {};

point_t::point_t(): x(0), y(0) {};

rect_t::rect_t(point_t l_, point_t r_): l(l_), r(r_) {};

adv_point::adv_point(point_t p): point(p), id(0), left_fr(0), right_fr(0) {};

adv_point::adv_point(int i): point(point_t()), id(i), left_fr(0), right_fr(0) {};

bool comp_x (point_t a, point_t b)
{
	return a.x < b.x;
}

bool comp_y (adv_point a, adv_point b)
{
	return a.point.y < b.point.y;
}

Node::Node(std::vector<point_t> &a)
{
	for (auto i = a.begin(); i < a.end(); i++)
		array.push_back(adv_point(*i));
	lf = a[0].x;
	rf = a[a.size() - 1].x;
	if (a.size() == 1)
	{
		left = right = NULL;
	}
	else
	{
		int k = a.size()/2;
		std::vector<point_t> l_a(k), r_a(a.size() - k);
		std::copy(a.begin(), a.begin() + k, l_a.begin());
		std::copy(a.begin() + k, a.end(), r_a.begin());
		left = new Node(l_a);
		right = new Node(r_a);
		std::sort(array.begin(), array.end(), comp_y);
		for (size_t i = 0; i < array.size(); i++)
			array[i].id = i;
		for (auto i = array.begin(); i < array.end(); i++)
		{
			auto p = std::lower_bound(left->array.begin(), left->array.end(), *i, comp_y);
			if (p == left->array.end())
				i->left_fr = left->array.size();
			else
				i->left_fr = (*p).id;
			p = std::lower_bound(right->array.begin(), right->array.end(), *i, comp_y);
			if (p == right->array.end())
				i->right_fr = right->array.size();
			else
				i->right_fr = p->id;
		}
	}
}

Node::Node(): lf(0), rf(0), left(NULL), right(NULL) {};

Node::~Node()
{
	delete left;
	delete right;
}

tree_t::tree_t(std::vector<point_t> &p)
{
	std::sort(p.begin(), p.end(), comp_x);
	root = new Node(p);
}

std::vector<point_t> x_search(Node *cur, double x_min, double x_max, int l, int r)
{
	if (cur->lf > x_max || cur->rf < x_min)
	{
		return std::vector<point_t>();
	}
	else
		if (cur->lf >= x_min && cur->rf <= x_max)
		{
			std::vector<point_t> a;
			for (int i = l; i < r; i++)
				a.push_back(cur->array[i].point);
			return a;
		}
		else
		{
			int size = cur->array.size();
			int ll, rl, lr, rr;
			if (l == size)
			{
				ll = cur->left->array.size();
				lr = cur->right->array.size();;
			}
			else
			{
				ll = cur->array[l].left_fr;
				lr = cur->array[l].right_fr;
			}
			if (r == size)
			{
				rl = cur->left->array.size();;
				rr = cur->right->array.size();;
			}
			else
			{
				rl = cur->array[r].left_fr;
				rr = cur->array[r].right_fr;
			}
			std::vector<point_t> a = x_search(cur->left, x_min, x_max, ll, rl);
			std::vector<point_t> b = x_search(cur->right, x_min, x_max, lr, rr);
			a.insert(a.begin(), b.begin(), b.end());
			return a;
		}
}

std::vector<point_t> tree_t::search_in_rect(rect_t rect)
{
	std::vector<point_t> ans;
	int l, r;
	auto p = std::lower_bound(root->array.begin(), root->array.end(), adv_point(point_t(0, rect.l.y)), comp_y);
	if (p == root->array.end())
		l = root->array.size();
	else
		l = p->id;
	p = std::upper_bound(root->array.begin(), root->array.end(), adv_point(point_t(0, rect.r.y)), comp_y);
	if (p == root->array.end())
			r = root->array.size();
		else
			r = p->id;
	ans = x_search(root, rect.l.x, rect.r.x, l, r);
	return ans;
}

tree_t::~tree_t()
{
	delete root;
}
